// Linear search

# include <iostream.h>
# include <conio.h>

class BinSearch {
  int size, key, flag, mid, bot, top;
  int a[100];
public:
  void get();
  void search();
};

void BinSearch::get() {
  cout << "Enter Array size: ";
  cin >> size;
  int i = 0;
  for(i = 0; i < size; i++) {
    cout << "Enter array element no." << i+1 << ": ";
    cin >> a[i];
  }
}

void BinSearch::search() {
  cout << "Enter the number to find: ";
  cin >> key;
  bot, flag = 0;
  top = size-1;
  while(bot <= top) {
    mid = (bot + top) / 2;
    if(a[mid] < key) {
       bot = mid + 1;
       mid = (bot + top) / 2;
    }
    else if(a[mid] > key) {
      top = mid - 1;
      mid = (bot + top) / 2;
    }
    if(a[mid] == key) {
      cout << "Match found!";
      flag++;
      break;
    }
  }
  if(!flag) {
    cout << "Not Found!";
  }
}

void main() {
  clrscr();
  BinSearch bs;
  bs.get();
  bs.search();
  getch();
}